public class 子数组的最小值之和 {

    public static int MOD = 1000000007; // 取值过大需要取模
    public static int MAXN = 30001; // 栈的长度最大值
    public static int[] stack = new int[MAXN]; // 存储的是下标
    public static int r; // 维护栈的长度
    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        r = 0;
        long ans = 0; // 返回值使用 long, 防止发生溢出
        for (int i = 0; i < n; i++) {
            // 单调栈来进行维护操作, 找出当前元素的两边最小值
            // 可以确保出当前元素到两边的边界元素之间的元素都大于 cur, 然后记录一下所有的范围
            // 其中需要注意元素相同的情况, 我们将前一个相同元素给弹出, 保留后一个元素
            // 因为后一个元素会补充前一个元素没有包含的范围
            while (r > 0 && arr[i] <= arr[stack[r - 1]]) {
                int cur = stack[--r]; // 弹出栈顶元素
                int left = r > 0 ? stack[r - 1] : -1; // 栈顶元素左边最小值的下标
                ans += (long)(cur - left) * (i - cur) * arr[cur]; // 算出以 cur 为最小值的范围
                ans %= MOD; // 防止溢出
            }
            stack[r++] = i; // 将当前元素压栈
        }
        // 清算阶段
        while (r > 0) {
            // 和前面是一样的, 唯一不同的是最右边是没有最小值的, 画个图理解一下 n - cur 这个范围即可
            int cur = stack[--r];
            int left = r > 0 ? stack[r - 1] : -1;
            ans += (long)(cur - left) * (n - cur) * arr[cur];
            ans %= MOD;
        }
        return (int)ans;
    }
}
